package com.atguigu.main.sort;

import java.util.Arrays;

/**
 * 插入排序算法
 *
 * @Author 剧情再美终是戏
 * @Date 2019/12/25
 * @return
 * @Version 1.0
 **/
public class InsertSort {

    public static void main(String[] args) {
        int[] array2 = {1, 3, 5, 2, 4, 9, 8, -1, 6};
        System.out.println(Arrays.toString(InsertSort.insertSort(array2)));
    }

    public static int[] insertSort(int[] arrays) {
        long startTime = System.currentTimeMillis();
        for (int i = 1; i < arrays.length; i++) {
            int insertVal = arrays[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && arrays[insertIndex] > insertVal) {
                arrays[insertIndex + 1] = arrays[insertIndex];
                insertIndex--;
            }
            if (arrays[insertIndex+1] != insertVal) {
                arrays[insertIndex+1] = insertVal;
            }
        }
        System.out.printf("插入排序算法\t耗时%dms\n", System.currentTimeMillis() - startTime);
        return arrays;
    }
}
